⟸ Go Back ⟸
Exercise 6 (Homework 2).
(regular languages, homomorphism, minimization of DFAs)

Homomorphism of a regular language is regular

  1. Compute explicitly the minimum DFA for the language \sigma(L), where

    1. L=\{axbya\mid x,y\in\{a,b\}^*\} and \sigma is the homomorphism defined by \sigma(a)=aa and \sigma(b)=ba.
    2. L=\{axbyc\mid x,y\in\{a,b,c\}^*\} and \sigma is the homomorphism defined by \sigma(a)=ab, \sigma(b)=b, and \sigma(c)=\lambda.
    3. L=\{xbcya\mid x,y\in\{a,b,c\}^*\} and \sigma is the homomorphism defined by \sigma(a)=bbb, \sigma(b)=a,, and \sigma(c)=\lambda.

    Compute the minimum DFA recognizing L. From that DFA construct a \lambda-NFA A recognizing the language \sigma(L). Now, using the power-set construction make A deterministic and minimize the DFA obtained.

    Recall that given a DFA A and a homomorphism \sigma, it is possible to construct an NFA recognizing the language \sigma(L(A)) by transforming each transition \ \stackrel{a}{\to}\ in A into \ \stackrel{\sigma(a)}{\to}\ in an extended automaton and converting each extended transition into a \lambda-NFA by adding new states.

  2. Given as input a DFA A, what is the cost of computing a DFA for \sigma(L(A))? Does the construction to obtain an NFA recognizing \sigma(L(A)) give a DFA?

  3. Does the construction to obtain an NFA recognizing \sigma(L(A)) still work if we started with an NFA A? In other words, if each transition \ \stackrel{a}{\to}\ in an NFA A is transformed into the extended transition \ \stackrel{\sigma(a)}{\to}\ and then converted into a \lambda-NFA by adding new states, does that give a correct \lambda-NFA for \sigma(L(A))?